package com.example.question.bt.backtrack2;


import java.util.ArrayList;
import java.util.List;

public class Code07_322 {


    public static void main(String[] args) {
        Code07_322 code = new Code07_322();
//        System.out.println("code.coinChange(new int[]{1, 2147483647}, 2) = " + code.coinChange(new int[]{/*1,*/ 2, 5}, 100));
        System.out.println("code.change(5, new int[]{1, 2, 5}) = " + code.change(5, new int[]{1, 2, 5}));
    }

    private int minCoins = Integer.MAX_VALUE;

    public int coinChange(int[] coins, int amount) {
        process(coins, amount, 0, 0);
        return minCoins == Integer.MAX_VALUE ? -1 : minCoins;
    }

    /**
     * todo 记忆化搜索改如何写？
     *
     * @param amount
     * @param sum
     * @param count
     */
    private void process(int[] coins, int amount, int sum, int count) {
        if (sum > amount || sum < 0) {
            return;
        }
        if (sum == amount) {
            minCoins = Math.min(minCoins, count);
            return;
        }
        for (int coin : coins) {
            sum += coin;
            count++;
            process(coins, amount, sum, count);
            sum -= coin;
            count--;
        }
    }


    public int change(int amount, int[] coins) {
        List<List<Integer>> result = new ArrayList<>();
        process1(coins, amount, 0, new ArrayList<>(), result);
        System.out.println(result);
        return anInt;
    }

    private int anInt;

    private void process1(int[] coins, int amount, int sum, List<Integer> path, List<List<Integer>> result) {
        if (sum > amount || sum < 0) {
            return;
        }
        if (sum == amount) {
            anInt += 1;
            result.add(new ArrayList<>(path));
            return;
        }
        // todo 这个如何剪枝
        for (int coin : coins) {
            path.add(coin);
            sum += coin;
            process1(coins, amount, sum, path, result);
            sum -= coin;
            path.remove(path.size() - 1);
        }
    }
}
